﻿#include <vector>
using namespace std;

class Solution {
public:
    // 根据题意，不能增加额外空间开销，数组必定存在，且所有元素都>=1且<=数组长度；即可以给指定pos元素，再不影响读取原本区段的值的情况下添加一个标记，最终判断标记即可得解。
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        const int len = nums.size();
        // 這裏做最簡單的+len處理，添加標記用;理論略，題解上有詳細說明。
        for (int i = 0; i < len; i++)
        {
            const int pos = (nums[i] - 1) % len;
            nums[pos] += len;
        }
        // 遍歷查詢求解
        vector<int> ans;
        for (int i = 0; i < len; i++) {
            if (nums[i] <= len)
                ans.push_back(i + 1);
        }
        return ans;
    }
};